<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
/* Template */

#include &lt;cstdio&gt;
#include &lt;cmath&gt;
#include &lt;algorithm&gt;

using namespace std;

/* Main part */

struct Tree2D
{
  int n, *mem, **t;

  void init( int _n, int *p )
  {
    n = _n, mem = new int[(int)ceil(n * (log(n) / log(2.0) + 1) + 1e-9)];
    t = new int* [2 * n];
    for (int i = n; i &lt; 2 * n; i++)
      t[i] = mem++, t[i][0] = p[i - n];
    for (int s = 1, l = (n + 1) / 2, r = (2 * n - 2) / 2; l &lt;= r; l = (l + 1) / 2, r = (r - 1) / 2, s *= 2)
      for (int i = l; i &lt;= r; i++)
        merge(t[2 * i], t[2 * i] + s, t[2 * i + 1], t[2 * i + 1] + s, t[i] = mem), mem += s * 2;
  }

  inline int inner_get( int i, int s, int x, int y )
  {
    return upper_bound(t[i], t[i] + s, y) - lower_bound(t[i], t[i] + s, x);
  }

  int get( int l, int r, int x, int y ) // 0 &lt;= l &lt;= r &lt; n, [l..r] * [x..y]
  {
    int cnt = 0, s;
    if (x &gt; y)
      return 0;
    for (l += n, r += n, s = 1; l &lt;= r; l &gt;&gt;= 1, r &gt;&gt;= 1, s &lt;&lt;= 1)
    {
      if ((l & 1) == 1) cnt += inner_get(l++, s, x, y);
      if ((r & 1) == 0) cnt += inner_get(r--, s, x, y);
    }
    return cnt;
  }
};

</code></pre>

</body>
</html>

<font style="visibility:hidden">
